package leetcode_1_200;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_152_shit {
    public static void main(String[] args) {
        System.out.println(maxProduct(new int[]{2, 3, -2, 4}));
        System.out.println(maxProduct(new int[]{-2,0,-1}));
        System.out.println(maxProduct(new int[]{-2}));
        System.out.println(maxProduct(new int[]{0, 2}));
    }
    private static int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        int[] ms = new int[n + 1];
        ms[0] = 1;
        int[] count = new int[n + 1];
        int tc = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0){
                ms[i + 1] = 1;
                tc = 0;
                list.add(i + 1);
            }
            if (nums[i] < 0){
                tc++;
            }
            if (nums[i] != 0)
                ms[i + 1] = ms[i] * nums[i];
            count[i + 1] = tc;
        }
        if (list.size() == 0){
            int l = 0, r = count.length - 1;
            if ((count[r] - count[l]) % 2 == 0){
                res = Math.max(res, ms[r] / ms[l]);
            }else {
                while (l < r){
                    if ((count[r] - count[l]) % 2 == 0){
                        break;
                    }
                    l++;
                }
                if (l == r){
                    res = Math.max(res, ms[r] / ms[r - 1]);
                }else {
                    res = Math.max(res, ms[r] / ms[l]);
                }
                l = 0;
                r = count.length - 1;
                while (l < r){
                    if ((count[r] - count[l]) % 2 == 0){
                        break;
                    }
                    r--;
                }
                if (r > l){
                    res = Math.max(res, ms[r] / ms[l]);
                }
            }
        }else {
            int l = 0, r;
            for (int i = 0; i <= list.size(); i++) {
                int index;
                if (i == list.size()){
                    index = n + 1;
                }else {
                    index = list.get(i);
                }
                r = index - 1;
                if (l == r){
                    res = Math.max(nums[l], res);
                    continue;
                }
                if ((count[r] - count[l]) % 2 == 0){
                    res = Math.max(res, ms[r] / ms[l]);
                }else {
                    while (l < r){
                        if ((count[r] - count[l]) % 2 == 0){
                            break;
                        }
                        l++;
                    }
                    if (l == r){
                        res = Math.max(res, ms[r] / ms[r - 1]);
                    }else {
                        res = Math.max(res, ms[r] / ms[l]);
                    }
                    while (l < r){
                        if ((count[r] - count[l]) % 2 == 0){
                            break;
                        }
                        r--;
                    }
                    if (l != 0 &&  l == r){
                        res = Math.max(res, ms[r] / ms[r - 1]);
                    }else {
                        res = Math.max(res, ms[r] / ms[l]);
                    }
                }
                l = index;
            }
        }
        return res;
    }
}
